我们应该用缩点,将原图变为图,同时记录每个强连通分量的节点个数,记为。
因为起点终点都是1,所以路径一定是一个环。我们可以处理出1到所有点的距离,存在中(跑正图)和所有点到1的距离存在中(跑反图)。注意,如果走不到就设为极小值。最短路跑的是点权,其实和边权差不多。
题目说可以逆向走一条有向边,我们设该边起点为,终点为,那么,答案就应为。
An Ac a day, keeps the doctor away!
我们应该用Tarjan缩点,将原图变为GAD图,同时记录每个强连通分量的节点个数,记为num[i]。
因为起点终点都是1,所以路径一定是一个环。我们可以处理出1到所有点的距离,存在dis1中(跑正图)和所有点到1的距离存在dis2中(跑反图)。注意,如果走不到就设为极小值。最短路跑的是点权,其实和边权差不多。
题目说可以逆向走一条有向边,我们设该边起点为u,终点为v,那么,答案就应为num[belong[1]]+max(dis1[v]+dis2[u])。
一道神奇的线段树...
题目要求区间修改,区间查询,很容易想到线段树,但是怎么维护每一位数字呢?
显然,我们将每位拆分,对于每一个数字维护他的贡献,如 1221123 中 1 的贡献为 1001100 , 2 的贡献为 110010。于是,我们需要10棵线段树,维护0−9的贡献。
显然,如果每次删一个点,答案可能会减小,而且你还不知道在哪里减小的...
所以我们反向思考,如果每次加一个点,那么答案肯定是不减的,而且如果答案变大,新矩阵一定包含该点。
up[i][j]表示以(i,j)为起点出发向上能到达的 ′. ′ 的个数。(遇到 ′X ′ 停止)
这道题显然是最短路,但是似乎转向时不好处理,于是我们要用到分层图。
实现很简单,建立两层图,第一层记录横向边,第二层记录纵向边,相同的关键点两层图连一条费用为1的边。
还有,这道题只需要在关键点之间连边(非关键点无法转向,连了也没用),路径长度为坐标差*2。
这道题貌似很多人用的是网络流+分层图。这里介绍一种费用流解法。
可以证明,最后一个人到达的时间是小于第100天的。
那么对于每一趟航班,如果他的起点是u,终点为v,可搭乘的人的数量为w。那我们就对(u,v)连100条流量为w,费用为i的边(i表示第几天),分别表示第i天的航班。